1. Field of the Invention
This invention relates to the field of computer aided design for digital circuits, particularly to modeling the timing characteristics of digital circuits which include latches. This invention is used for designing and verifying the functionality of digital circuits before they are fabricated. In particular, the invention aids in the problem of simulation and verification of the timing behavior of a digital circuit.
2. Statement of the Related Art
Timing Verification
Timing verification takes two forms. "Timing simulation" verifies the behavior of an electronic circuit by emulating the circuit's function via a computer program. Stimulus is presented to the program and the program is expected to behave in a manner similar to the intended circuit. "Static timing analysis" uses a computer program to analyze the structure of the circuit by analyzing a representation stored in memory. The analysis determines the worst possible timing behavior for the circuit and compares that behavior to the worst acceptable behavior to check for discrepancies.
In both timing verification schemes, "timing models" are sometimes used. Timing models are blocks of computer data which can be used to recreate the timing behavior of an electronic circuit. Timing models can vary in complexity, depending on the of circuit they represent, ranging from a single transistor to an entire computer system. Timing models also vary in size (amount of space they take in a computer memory) and accuracy. In general, the more accurate or complex a model, the bigger it will be. Timing models are generally represented as simplified circuits in both types of computer program. Thus, the program can use the same routines for both the original circuit and the timing model.
It is of interest to make the size of timing models as small as possible for a given complexity of circuit, while maintaining the accuracy of the model. In general, a smaller model will not only require less space in a computer memory, but also will be faster for a computer to evaluate. Often, a model's accuracy will be sacrificed to shrink the model and speed its evaluation. This is especially important for large models which represent an entire subcircuit of an electronic system.
Port-to-Port Timing Models
A popular technique for shrinking a timing model involves the creation of a "port-to-port" model. This technique involves analyzing an electronic circuit to isolate and maintain only the timing behavior that can be observed at the circuit's connections to surrounding circuits (the "connections" are often called "ports"). So any timing behavior of a circuit that is only internal to that circuit is discarded, leaving only the information which is essential to verifying the timing behavior of the circuit in the context of surrounding circuits. Port-to-port timing models have been used in both timing simulation and static timing analysis. The models are accurate, and generally provide good compression of model size.
FIG. 2 is a block diagram showing a representation in memory of a digital circuit which contains a multiplicity of input signals (201, 202, 203, 204 ), output signals (205, 206, 207, 208 ), combinational logic (209, 210, 211), and edge-triggered (or master-slave) flip-flops (212, 213). A flip-flop is an electronic device which is controlled by a clock signal. At the instant the value of its clock signal changes, a flip-flop passes the value of its data signal to its output signal. At other times, the flip-flop holds the value of its output signal constant. The connecting lines in FIG. 2 represent electrical connections in the circuit. A port-to-port timing model can be used to represent this digital circuit as shown in FIG. 3 and FIG. 4.
In port-to-port modeling, the electronic circuit is analyzed to determine the longest time that it will take for an electronic signal to pass from each input port to each output port. Often the shortest time is determined as well. A flip-flop in the circuit acts much like an internal port and is also considered a start point and an end point for electronic signals. Analysis is also done to determine the longest time that it will take for an electronic signal to pass from each input port to the input signals of each flip-flop and from the output signal of each flip-flop to each output port. Once this analysis has taken place, the details of the combinational logic are no longer necessary and can be discarded, resulting in a "partial port-to-port" model as shown in FIG. 3.
Edge triggered flip-flops have the property of being controlled by an electronic signal called a "clock". When this clock signal changes voltage levels, all flip-flops which are controlled by that clock perform their function. Because many flip-flops connected to a single clock function simultaneously, the flip-flops connected to a single clock many be "collapsed" into one flip-flop 414 in the port-to-port timing model. The result is a "fill port-to-port" model as shown in FIG. 4, where only the longest path between pins and the single collapsed flip-flop is important Because there are usually a multitude of flip-flops in an electronic circuit, collapsing flip-flops results in a large compression of the model's size.
There are many digital circuits that use a device called a "transparent latch" in place of flip-flops. Like a flip-flop, a transparent latch, also called a "latch", is controlled by a clock signal. Flip-flops are active only at the instant its clock signal changes; a latch is can be active at any time that its clock signal remains at a high voltage. Some latches are active when there clock signals are at low voltage, instead of high voltage, but the processes are the same. The remainder of this document discusses latches that are transparent when the clock is high but it will be apparent to one skilled in the art that the techniques described also apply to latches that pass values when the clock is low.
When the clock signal transitions from high to low the latch "latches" the input data and holds that value on the output until the clock transitions back to high again. The input data is fed to the latch via the latch's "D pin." The D pin may also be called the "data pin." The output of the latch is available on the latch's "Q pin." The clock signal is connected to the latch via the "clock pin."
Due to the physical characteristics of the electronic circuitry from which physical latches are implemented, the transition between when the latch is transparent and when it holds its value is not instantaneous. Therefore, the value on the data pin must be available a certain amount of time before the clock signal transitions to a low voltage. This time is called the "setup time." Routines that verify that the data is available early enough to meet the setup time are called "setup checks" and violations are called "setup violations." In addition to the setup time, the data value must remain constant for a certain amount of time after the clock transitions to low. This time is called the "hold time." Routines that verify that the data is available long enough to meet the hold time are called "hold checks" and violations are called "hold violations." If a setup or a hold violation occurs, the latch might not contain a valid value. Thus, it is important that models accurately represent setup and hold times.
Conventionally, full port-to-port models have not been used to model electronic circuits which incorporate transparent latches. For circuits which contain transparent latches, conventional methods of generating port-to-port timing models use one of two techniques.
For one technique, partial port-to-port models are used, and all transparent latches of the original circuit are maintained in the model. This results in a model which is larger and slower to evaluate than a full port-to-port model.
In an alternate technique, the latches in the circuit are converted either to combinational logic or to edge-triggered flip-flops, and then normal port-to-port modeling techniques are applied. Using this technique, the full or partial port-to-port model will reproduce the timing behavior of the original electronic circuit only under a subset of possible stimuli. This means that the model is inaccurate, and the model might conservatively suggest that the modeled circuit has bad timing when the circuit might actually be correct.
The reason that this second technique produces models that are too pessimistic is that the latches in a circuit can "time borrow" amongst themselves. Time borrowing is possible when the combinational logic between two latches requires more time than the clock period to compute a stable value. However, if the logic following the second latch requires less than an entire clock period to compute a stable value, then the value computed by the first pair of latches need not become stable until some time after the clock signal goes high. The second set of logic will still have enough time to compute a stable value, even though its calculations did not begin until some time after the clock signal went high. Time borrowing is an essential technique for latch-based design. However, models based on latches which are converted to combinational logic or edge-triggered flip-flops do not include sufficient information to allow time borrowing.